{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Get all Values at a Certain Height in a Binary Tree\n",
    "\n",
    "[原题](https://mp.weixin.qq.com/s/jxePPAAKOr6b7OZ8f5onHg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question\n",
    "\n",
    "Given a binary tree, return all values given a certain height `h`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example\n",
    "\n",
    "A tree that seems like this should return a list `[4, 5, 7]` at a quering level of `3`.\n",
    "\n",
    "```text\n",
    "#     1\n",
    "#    / \\\n",
    "#   2   3\n",
    "#  / \\   \\\n",
    "# 4   5   7\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "''' Class Definition '''\n",
    "class Node():\n",
    "    def __init__(self, value, left=None, right=None):\n",
    "        self.value = value\n",
    "        self.left = left\n",
    "        self.right = right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "''' Algorithm '''\n",
    "def valuesAtHeight(root, height):\n",
    "    # If there's an empty tree, return None directly.\n",
    "    if root is None:\n",
    "        return None\n",
    "    \n",
    "    # Create a traversal queue to record elements of each height.\n",
    "    queue = [(root, 1)]\n",
    "    \n",
    "    # Stop when the first element reaches the quering height.\n",
    "    while queue[0][1] != height:\n",
    "        # Check if the first element has a left subree.\n",
    "        if queue[0][0].left is not None:\n",
    "            # Add its left child to the end of the queue.\n",
    "            # Also, its height should be deeper.\n",
    "            queue.append((queue[0][0].left, queue[0][1] + 1))\n",
    "            \n",
    "        # The same as its right child.\n",
    "        if queue[0][0].right is not None:\n",
    "            queue.append((queue[0][0].right, queue[0][1] + 1))\n",
    "            \n",
    "        # Pop the first element of the queue.\n",
    "        queue.remove(queue[0])\n",
    "    \n",
    "    # Return the value of all elements left in the queue.\n",
    "    return [k[0].value for k in queue]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 5, 7]\n"
     ]
    }
   ],
   "source": [
    "''' Main Script '''\n",
    "a = Node(1, Node(2, Node(4), Node(5)), Node(3, right=Node(7)))\n",
    "print(valuesAtHeight(a, 3))\n",
    "# [4, 5, 7]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notes\n",
    "\n",
    "This question has a similar algorithm to Level Order Traversal (short for *LOT*). They both use a queue to realize, but this time we attach the node with its height together as a tuple and push/pop them together in the queue. After searching all previous level, the height of the first element should be the same as quering height. Then, elements left in the queue are what we need."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
